In many applications, it is necessary for one process executing on a computer system to communicate with one or more other processes executing on the same or other computer systems. The mechanism used to carry out these communications varies from system to system. One mechanism that has facilitated process-to-process communication in a variety of systems is a message queue. Processes send information to other processes by enqueuing messages in the message queue. The receiving processes obtain the information by dequeuing the messages from the message queue. Typically, these messages are read in a first-in first-out manner. Implementations of message queues are described in U.S. Pat. No. 7,181,482, U.S. Pat. No. 7,185,033, U.S. Pat. No. 7,185,034, U.S. Pat. No. 7,203,706, U.S. Pat. No. 7,779,418, U.S. Pat. No. 7,818,386, U.S. Pat. No. 7,680,793, U.S. Pat. No. 6,058,389, and U.S. Pat. No. 8,397,244, the contents of which are incorporated herein by reference in their entirety.
A message queue may be implemented in memory or on secondary storage, such as a magnetic disk, optical disk, or solid-state drive, or any other persistent secondary storage. An in-memory message queue allows queue operations to take place in memory, thereby reducing I/O latency. However, memory is generally a more limited resource. Thus, it may not always be assumed that a message queue can be completely implemented in memory.
An in-memory message cache that is backed by secondary storage may be used to store at least a portion of the messages in the message queue in memory. For example, database-backed queues may be architected to handle extremely large queues, even when aggregate queue size is many times larger than the size of the available memory. In a database-implemented message queue, an enqueuing process uses a connection to the database, or an enqueue session, to enqueue messages, and dequeuers use dequeue sessions to dequeue messages.
Conventional implementations of message queues do not scale well. Specifically, as the number of dequeue sessions increases, the contention for the “hot” messages at the head of the queue increases, thereby degrading performance. In addition, when the enqueue sessions and dequeue sessions are spread across several systems, the amount of communication on the network and/or interconnect between systems can become excessive.
Sharded queues address some of these issues. A sharded queue includes one or more shards. Within each shard, the messages are ordered based on enqueue time. However, no message order is enforced between shards. Typically, a dequeue session dequeues messages from each shard in a first-in first-out order. However, no dequeue order is enforced between shards. Implementations of sharded queues are described in U.S. Patent Application Pub. No. 2014/0372486, U.S. Patent Application Pub. No. 2014/0372489, and U.S. Patent Application Pub. No. 2014/0372702, the contents of which are incorporated herein by reference in their entirety.
Various caching algorithms exist for selecting a subset of data to store in memory. These algorithms include suboptimal algorithms, such as first-in, first-out (FIFO) and least recently used (LRU), as well as optimal algorithms, such as optimal page replacement (OPT) for virtual memory swapping. However, these techniques are not directly transferrable to a sharded queue where no enqueue order or dequeue order is enforced between shards, and/or to a multi-dequeuer queue where multiple dequeuers can potentially dequeue messages from any shard. For example, such algorithms are not designed to accommodate multiple enqueuers, multiple dequeuers, and/or multi-sharded queues. Furthermore, optimal algorithms require certain information to be known that cannot be readily ascertained in a queue with multiple shards and multiple dequeuers. For example, the OPT algorithm requires the sequence of page accesses to be known.
Thus, there is a need for optimal message cache management for message queues.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.